package _07_分治;

public class Main {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4 };
        //System.out.println(maxSubArray(nums));
        System.out.println(maxSubArray(nums));
    }


    static int maxSubArray(int[] nums){
        if(nums == null || nums.length==0) return 0;
        return maxSubArray(nums,0,nums.length);
    }

    /**
     * 分治
     * 求解[begin, end)中最大连续子序列的和
     * T(n) = T(n/2) + T(n/2) + O(n)
     * T(n) = 2T(n/2) + O(n)
     * logba = 1  d = 1
     * 函数定义：计算begin,end之间最大的连续子序列的和
     */
    static int maxSubArray(int[] nums,int begin,int end) {
        if(end - begin <2) return nums[begin]; //base case,当分割后的子数组元素只有一个的时候，返回begin或者end都可以
        int mid = (begin + end) >> 1;

        /*可能的解情况分为三种：
            1.子序列在[begin,mid)中
            2.子序列在[mid,end)中
            3.子序列在[begin,mid),[mid,end)都存在
        */
        int leftMax = Integer.MIN_VALUE; //左半部分最大值，左闭右开，取不到mid,
        int leftSum = 0; //计算左半部分的整数和
        for(int i=mid-1;i>=begin;i--){
            leftSum += nums[i];
            leftMax = Math.max(leftMax,leftSum); //求出左半部分最大值
        }

        int rightMax = Integer.MIN_VALUE; //右半部分最大值
        int rightSum = 0;
        for(int i=mid;i<end;++i){
            rightSum += nums[i];
            rightMax = Math.max(rightMax,rightSum); //求出右半部分最大值
        }

        //递归计算全部在左边和全部在右边的子序列和谁大，在和在中间的情况比较
        return Math.max(leftMax+rightMax,
               Math.max(maxSubArray(nums,begin,mid),
                       maxSubArray(nums,mid,end)));

    }

    //暴力枚举法
    static int maxSubArray1(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        //两个指针，begin和end,
        for(int begin = 0;begin<nums.length;++begin){
            int sum = 0; //为区间[begin,end]的和
            for(int end = begin;end< nums.length;++end){
                sum += nums[end];
                max = Math.max(max,sum);
            }
        }
        return max;
    }
}
